class TrieNode:
    def __init__(self, passed=0, ended=0):
        self.passed = passed
        self.ended = ended
        self.children = {}


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        current = self.root
        current.passed += 1
        for char in word:
            if char not in current.children:
                current.children[char] = TrieNode()
            current = current.children[char]
            current.passed += 1
        current.ended += 1

    def search(self, word):
        current = self.root
        for char in word:
            if char not in current.children:
                return 0
            current = current.children[char]
        return current.ended

    def startsWith(self, prefix):
        current = self.root
        for char in prefix:
            if char not in current.children:
                return 0
            current = current.children[char]
        return current.passed

    def remove(self, word):
        time = self.search(word)
        # 不存在直接返回
        if time == 0:
            return

        current = self.root
        current.passed -= 1
        for char in word:
            child = current.children[char]
            child.passed -= 1
            if child.passed == 0:
                # 当这条路只有这个单词了，要删除这个单词，那直接把这条路都给删了
                del current.children[char]
                return
            current = child
        current.ended -= 1
